﻿

namespace Common.Algorithm.Core;
public class PrimService
{
    private List<GraphEdge> _treeEdges = new List<GraphEdge>();

    public IList<GraphEdge> RunAlgm(int rootIndex, IEnumerable<GraphEdge> edges)
    {
        edges = edges.Where(e => e.weight != 0);

        List<GraphEdge> treeEdges = new List<GraphEdge>();

        List<int> treeIds = new List<int>();
        List<int> leafIds = new List<int>();

        leafIds = edges
            .GroupBy(e => e.stVertexId)
            .Select(g => g.First())
            .Select(e => e.stVertexId).ToList(); ;

        //READY
        treeIds.Add(rootIndex);
        leafIds.Remove(rootIndex);

        //START
        int maxCount = 100;
        while (maxCount > 0)
        {
            maxCount--;

            if (leafIds.Count == 0) break;

            double minWeight = double.MaxValue;
            GraphEdge minEdge = edges.First();
            foreach (var treeId in treeIds)
            {
                foreach (var leafId in leafIds)
                {
                    var curEdge = edges.At(treeId, leafId);
                    if (curEdge == null) { continue; }
                    if (curEdge.weight < minWeight)
                    {
                        minWeight = curEdge.weight;
                        minEdge = curEdge;
                    }
                }
            }
            treeEdges.Add(minEdge);
            treeIds.Add(minEdge.edVertexId);
            leafIds.Remove(minEdge.edVertexId);
        }
        _treeEdges = treeEdges;
        return treeEdges;

    }

    public IList<TreeNode> GetTreeEntity()
    {
        List<TreeNode> treeNodes = new List<TreeNode>();
        List<GraphEdge> treeEdges = _treeEdges;

        foreach (var group in treeEdges.GroupBy(t => t.stVertexId))
        {
            TreeNode node = new TreeNode();
            node.id = group.First().id;
            node.childIds.AddRange(group.Select(g => g.edVertexId));
            treeNodes.Add(node);
        }

        return treeNodes;
    }

    public struct TreeNode
    {
        public TreeNode()
        {
            this.id = 0;
            this.guid = Guid.NewGuid() ;
            this.childIds = new List<int>();
        }

        public int id { get; set; }
        public Guid guid { get; set; }
        public List<int> childIds { get; set; }
    }

}
